package Demo44;

import java.util.Arrays;
/*
    颜色分类
    https://leetcode.cn/problems/sort-colors/submissions/537031910/
    这里主要用到移动零的思想
    三指针
    用 3 个指针将 数组划分成 4个区域
    0 到 left 是 0
    left 到 i 是 1
    i 到 right 是待扫描
    right 到 len -1 是2

    我们有一个注意的点, 就是 nums[i] > 1 ,交换的时候, i 不能++
    因为是 i 和  right-1 但是 i 到 right 是待扫描 区域, 所以 i 不能++
 */

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        for(int left = -1,right = len,i = 0; i < right;i++) {
            if(nums[i] != 1) {
                if(nums[i] < 1) {
                    left++;
                    int tmp = nums[left];
                    nums[left] = nums[i];
                    nums[i] = tmp;
                }else {
                    right--;
                    int tmp = nums[right];
                    nums[right] = nums[i];
                    nums[i] = tmp;
                    i--;
                }
            }
        }
        for(int n : nums) {
            System.out.print(n + "");
        }
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.sortColors(new int[] {1,2,0});
    }
}